package Sort;

import java.util.Arrays;

/**
 * 时间复杂度：最差O(n^2) 平均O(nlog(n)) 最好O(nlog(n))
 * 空间复杂度：O(n) （可以使用尾递归优化降到O(log(n))）
 */
public class 快速排序 {
    public static void quickSort(int[] nums, int left, int right) {
        // 子数组长度为 1 时终止递归
        if (left >= right) return;
        // 哨兵划分
        int base = partition(nums, left, right);
        // 递归左子数组、右子数组
        quickSort(nums, left, base - 1);
        quickSort(nums, base + 1, right);
    }

    /* 哨兵划分 */
    private static int partition(int[] nums, int left, int right) {
        // 以 nums[left] 为基准数（优化：可在数组中选三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选元素的中位数作为基准数）
        int base = left;
        while (left < right) {
            while (left < right && nums[right] >= nums[base]) right--; // 从右向左找首个小于基准数的元素
            while (left < right && nums[left] <= nums[base]) left++; // 从左向右找首个大于基准数的元素
            swap(nums, left, right); // 交换这两个元素
        }
        swap(nums, left, base);  // 将基准数交换至两子数组的分界线
        return left;             // 返回基准数的索引
    }

    /* 元素交换 */
    private static void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{-5, 7, 1, 3, -7, 1, -3, -1, 10, 0, -4, 0, 5, 2, -3, 0, 9, 8};
        quickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
}
